Gra

Limit pamięci: 32 MB

Plansza do gry składa się z kolejno ponumerowanych pól. Na planszy znajduje się czarnych pionków i białych. Czarne pionki są rozmieszczone na początkowych polach planszy (na polach o numerach od 1 do ), natomiast białe na końcowych polach (na polach o numerach od do ). Pole o numerze jest początkowo wolne.

a. początkowe ustawienie pionków na planszy dla i możliwe ruchy,
b. plansza po wykonaniu ruchu pionkiem z pola 5 i możliwe ruchy

Na planszy można wykonywać dwa rodzaje ruchów polegających na przesunięciu pionka na sąsiednie wolne pole, albo na przeskoczeniu pionkiem nad sąsiednim pionkiem odmiennego koloru i wylądowaniu na wolnym polu.

Celem gry jest zamiana miejscami pionków czarnych i białych (tzn. rozmieszczenie czarnych pionków na polach o numerach od do , a białych na polach o numerach od 1 do ). Interesuje nas najkrótszy ciąg dozwolonych wyników wystarczających do zreazlizowania tego celu.

Zadanie

Napisz program, który:

• wczyta liczbę oznaczającą liczbę czarnych pionków na planszy,
• wyznaczy najkrótszy ciąg ruchów realizującą cel gry,
• wypisze wynik.

Wejście

W jedynym wierszu wejścia znajduje się liczba całkowita ().

Wyjście

W pierwszym wierszu wyjścia należy wypisać liczbę oznaczająca minimalną liczbę ruchów wystarczających do tego, aby doprowadzić pionki na planszy do konfiguracji końcowej. W kolejnych wierszach należy zapisać po jednej liczbie z przedziału . Liczba znajdująca się w -szym wierszu (dla ) oznacza numer pola, z którego należy przesunąć pionek w -tym ruchu.

Jeśli istnieje więcej niż jedno rozwiązanie, Twój program może wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

1

poprawną odpowiedzią jest:

3
1
3
2

Autor zadania: Tomasz Idziaszek.